package nf;

import java.util.*;
import java.util.concurrent.*;

import nf.traversal.*;
import nf.utility.*;
import nf.graph.*;
import nf.util.*;

public class DensityStability
{
	public static void main(String[] args)
	{
		final int n = 10;
		
		final double lowDensity = (n-1)/2;
		final double highDensity = n-1;
		final int binCount = (int)((highDensity - lowDensity) * 4);
		final double binSize = (highDensity - lowDensity) / (double)binCount;
		
		final int[] stableCount = new int[binCount];
		
		final List<Graph> qualifyingGraphs = new ArrayList<Graph>();
		
		FormationGame game = new FormationGame(null,
									new SimpleUtilityCalculator());
		
		int procs = Runtime.getRuntime().availableProcessors();
				
		class SDChecker implements Runnable
		{
			int numberToRun;
			public int considered;

			public SDChecker(int numberToRun)
			{
				this.numberToRun = numberToRun;
			}
			public void run()
			{
				FormationGame game = new FormationGame(null,
									new SimpleUtilityCalculator());
			
				for (considered = 0; considered < numberToRun; considered++) {
					Graph graph = GraphGenerator.generateRandomGraph(n);

					double density = graph.getAverageDegree();
					if (density >= lowDensity && density <= highDensity) {
						List<Rational> bounds = game.getCostBounds(graph);
						boolean stable = false;
						if (!bounds.get(1).lessThan(bounds.get(0)))
							stable = true;
				
						if (stable) {
							int bin = (int)(density / binSize);
							
							synchronized (qualifyingGraphs) {
								qualifyingGraphs.add(graph);
							}
							synchronized (stableCount) {
								stableCount[bin]++;
							}
						}
					}
				}
			}
		}
		
		ExecutorService runner = Executors.newFixedThreadPool(procs);
		ArrayList<SDChecker> checkers = new ArrayList<SDChecker>();
		
		int numberToRun = 1000;
		for (int i = 0; i < procs; i++) {
			SDChecker ch = new SDChecker(numberToRun / procs);
			checkers.add(ch);
			runner.execute(ch);
		}
		
		runner.shutdown();
		try {
			while (!runner.awaitTermination(1, TimeUnit.SECONDS)) {
				int	totalConsidered = 0;
				for (int i = 0; i < procs; i++) {
					totalConsidered += checkers.get(i).considered;
				}
				System.err.print("\rConsidered " + totalConsidered +
					" out of " + numberToRun + 
					" graphs. Stored " + qualifyingGraphs.size() + "        ");
			}
		} catch (InterruptedException e) { }
		
		
		//Output Data
		
		for (int i = 0; i < binCount; i++) {
			System.out.println(i + "\t" + (lowDensity + i * binSize) + "\t" + stableCount[i]);
		}
		
		System.out.println("Found " + qualifyingGraphs.size() + 
				" stable graphs with density between " + lowDensity + 
				" and " + highDensity);
				
		for (Graph g : qualifyingGraphs) {
			Simulator.printNetwork(game, g);
		}
	}
}
